package com.weixiao.leetcode;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

/**
 * 不同整数的最少数目
 * 给你一个整数数组 arr 和一个整数 k 。现需要从数组中恰好移除 k 个元素，请找出移除后数组中不同整数的最少数目。
 */
import static java.util.Arrays.sort;
public class Test1 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int[] arr = new int[6];
        System.out.println("请输入数组：");
        for (int i = 0; i < 6; i++) {
            arr[i] = scanner.nextInt();
        }
        System.out.println("请输入数字：");
        int k = scanner.nextInt();
        System.out.println(findLeastNumOfUniqueInts(arr, k));
    }

    public static int findLeastNumOfUniqueInts(int[] arr, int k) {
        Map<Integer,Integer> map=new HashMap();
        for(int i=0;i<arr.length;i++){
            //遍历数组，将数组中每个数字的个数存入map
            Integer x = map.get(arr[i]);
            if(x==null){
                map.put(arr[i],1);
            }else{
                map.put(arr[i],x+1);
            }
        }

        Integer[] a= new Integer[map.size()];
        int i=0;
        //将map中每个字符的个数存入数组，并排序
        for (int value : map.values()) {
            a[i]=value;
            i++;
        }
        sort(a);
        //循环k次，从第一个数字开始，每次将数字减一，最后得到减完之后还剩下多少个非0数字
        while (k > 0) {
            for (int j = 0; j < a.length; j++) {
                if (a[j] > 0) {
                    a[j]=a[j]-1;
                    break;
                }
            }
            k--;
        }
        //统计还剩下多少个非0的数字，得到结果
        int z=0;
        for (int j = 0; j < a.length; j++) {
            if (a[j] != 0) {
                z++;
            }
        }
        return z;
    }
}
